package binPack.skylineBinPack
{
	import binPack.*;
	import binPack.DisjointRectCollection;
	import binPack.SkylineNode;
	import binPack.guillotine.FreeRectChoiceHeuristic;
	import binPack.guillotine.GuillotineBinPack;
	import binPack.guillotine.GuillotineSplitHeuristic;
	
	import flash.geom.Rectangle;

	/** 
	 *
	 * brief Implements different bin packer algorithms that use the SKYLINE data structure.
	 * This work is released to Public Domain, do whatever you want with it.
	 *  @author Jukka Jylänki
	 * @see https://github.com/juj/RectangleBinPack/blob/master/SkylineBinPack.h
	 */
	public class SkylineBinPack
	{
		private var binWidth:int;
		private var binHeight:int;
		private var disjointRects:DisjointRectCollection;
		private var skyLine:Vector.<SkylineNode> = new Vector.<SkylineNode>();
		
		private var usedSurfaceArea:uint;
		
		/// If true, we use the GuillotineBinPack structure to recover wasted areas into a waste map.
		private var useWasteMap:Boolean;
		private var wasteMap:GuillotineBinPack;
		public function SkylineBinPack(width:int=0, height:int=0, useWasteMap:Boolean=false)
		{
			Init(width, height, useWasteMap);
		}
		
		private function Init( width:int,  height:int,  useWasteMap_:Boolean):void
		{
			binWidth = width;
			binHeight = height;
			useWasteMap = useWasteMap_;
			wasteMap = new GuillotineBinPack();
			if( Config.DEBUG){
				disjointRects = new DisjointRectCollection();
			}
			
			usedSurfaceArea = 0;
			while( skyLine.length)
				skyLine.pop();
			var node:SkylineNode = new SkylineNode();
			node.x = 0;
			node.y = 0;
			node.width = binWidth;
			skyLine.push(node);
			
			if (useWasteMap)
			{
				wasteMap.Init(width, height);
				var arr = wasteMap.GetFreeRectangles();
				while(arr.length != 0){
					arr.pop();
				}
			}
		}
		
		private function InsertRects(rects:Vector.<RectSize>, dst:Vector.<Rect>,  method:int):void{
			while(dst.length!=0){
				dst.pop();
			}
				
			while(rects.length > 0){
				var bestNode:Rectangle;
				var bestScore1:int = int.MAX_VALUE;
				var bestScore2:int = int.MAX_VALUE;
				var bestSkylineIndex:int = -1;
				var bestRectIndex:int = -1;
				for(var i:int = 0; i < rects.length; ++i)
				{
					var newNode:Rectangle;
					var score1:int;
					var score2:int;
					var index:int;
					var result:*;
					switch(method)
					{
						case LevelChoiceHeuristic.LevelBottomLeft:
							result =  FindPositionForNewNodeBottomLeft(rects[i].width, rects[i].height, score1, score2, index);
							newNode = result.node;
							score1 = result.bw;
							score2 = result.bh;
							index = result.bi;
							trace('SkylineBinPack.Insert.LevelBottomLeft',disjointRects.Disjoint(newNode));
							break;
						case LevelChoiceHeuristic.LevelMinWasteFit:
							result = FindPositionForNewNodeMinWaste(rects[i].width, rects[i].height, score2, score1, index);
							newNode = result.node;
							score1 = result.r0;
							score2 = result.r1;
							index = result.r2;
							trace('SkylineBinPack.Insert.LevelMinWasteFit',disjointRects.Disjoint(newNode));
							break;
						default: 
							break;
					}
					if (newNode.height != 0)
					{
						if (score1 < bestScore1 || (score1 == bestScore1 && score2 < bestScore2))
						{
							bestNode = newNode;
							bestScore1 = score1;
							bestScore2 = score2;
							bestSkylineIndex = index;
							bestRectIndex = i;
						}
					}
				}
				
				if (bestRectIndex == -1)
					return;
				
				// Perform the actual packing.
				if( Config.DEBUG){
					trace('SkylineBinPack.Insert.disjointRects',disjointRects.Disjoint(bestNode));
					disjointRects.Add(bestNode);
				}
				
				
				AddSkylineLevel(bestSkylineIndex, bestNode);
				usedSurfaceArea += rects[bestRectIndex].width * rects[bestRectIndex].height;
				rects.splice( bestRectIndex,1);
				dst.push(bestNode);
			}
		}
		
		public function Insert(width:int, height:int, method:int):Rectangle{
			// First try to pack this rectangle into the waste map, if it fits.
			var node:Rectangle = wasteMap.Insert(width, height, true, FreeRectChoiceHeuristic.RectBestShortSideFit, GuillotineSplitHeuristic.SplitMaximizeArea);
			trace('Insert 1',disjointRects.Disjoint(node));
			
			if (node.height != 0)
			{
				var newNode:Rectangle;
				newNode.x = node.x;
				newNode.y = node.y;
				newNode.width = node.width;
				newNode.height = node.height;
				usedSurfaceArea += width * height;
				if( Config.DEBUG){
					trace('Insert 2',disjointRects.Disjoint(newNode));
					disjointRects.Add(newNode);
				}
				return newNode;
			}
			
			switch(method)
			{
				case LevelChoiceHeuristic.LevelBottomLeft: 
					return InsertBottomLeft(width, height);
				case LevelChoiceHeuristic.LevelMinWasteFit: 
					return InsertMinWaste(width, height);
				default: 
					//assert(false); 
					return node;
			}
		}
		
		public function RectangleFits( skylineNodeIndex:int, width:int, height:int,  y:int):Object
		{
			var x:int = skyLine[skylineNodeIndex].x;
			if (x + width > binWidth)
				return false;
			var widthLeft:int = width;
			var i:int = skylineNodeIndex;
			y = skyLine[skylineNodeIndex].y;
			while(widthLeft > 0)
			{
				y = Math.max(y, skyLine[i].y);
				if (y + height > binHeight)
					return false;
				widthLeft -= skyLine[i].width;
				++i;
				trace(i < skyLine.length || widthLeft <= 0);
			}
			return {b:true,y:y};
		}
		
		public function ComputeWastedArea( skylineNodeIndex:int, width:int, height:int, y:int):int{
			var wastedArea:int = 0;
			var rectLeft:int = skyLine[skylineNodeIndex].x;
			var rectRight:int = rectLeft + width;
			for(; skylineNodeIndex < skyLine.length && skyLine[skylineNodeIndex].x < rectRight; ++skylineNodeIndex)
			{
				if (skyLine[skylineNodeIndex].x >= rectRight || skyLine[skylineNodeIndex].x + skyLine[skylineNodeIndex].width <= rectLeft)
					break;
				
				var leftSide:int = skyLine[skylineNodeIndex].x;
				var rightSide:int = Math.min(rectRight, leftSide + skyLine[skylineNodeIndex].width);
				trace('ComputeWastedArea',y >= skyLine[skylineNodeIndex].y);
				wastedArea += (rightSide - leftSide) * (y - skyLine[skylineNodeIndex].y);
			}
			return wastedArea;
		}
		
		public function RectangleFits1(skylineNodeIndex:int, width:int, height:int,  y:int,  wastedArea:int):Object
		{
			var result:* = RectangleFits(skylineNodeIndex, width, height, y);
			var fits = result.b;
			y = result.y;
			if (fits)
				wastedArea = ComputeWastedArea(skylineNodeIndex, width, height, y);
			
			return {f:fits,y:y,w:wastedArea};
		}
		
		private function AddWasteMapArea(skylineNodeIndex:int, width:int, height:int, y:int):void
		{
			// int wastedArea = 0; // unused
			const rectLeft:int = skyLine[skylineNodeIndex].x;
			const rectRight:int = rectLeft + width;
			for(; skylineNodeIndex < skyLine.length && skyLine[skylineNodeIndex].x < rectRight; ++skylineNodeIndex)
			{
				if (skyLine[skylineNodeIndex].x >= rectRight || skyLine[skylineNodeIndex].x + skyLine[skylineNodeIndex].width <= rectLeft)
					break;
				
				var leftSide:int = skyLine[skylineNodeIndex].x;
				var rightSide:int = Math.min(rectRight, leftSide + skyLine[skylineNodeIndex].width);
				trace(y >= skyLine[skylineNodeIndex].y);
				
				var waste:Rectangle;
				waste.x = leftSide;
				waste.y = skyLine[skylineNodeIndex].y;
				waste.width = rightSide - leftSide;
				waste.height = y - skyLine[skylineNodeIndex].y;
				
				trace(disjointRects.Disjoint(waste));
				wasteMap.GetFreeRectangles().push(waste);
			}
		}
		
		private function AddSkylineLevel(skylineNodeIndex:int, rect:Rectangle):void
		{
			// First track all wasted areas and mark them into the waste map if we're using one.
			if (useWasteMap)
				AddWasteMapArea(skylineNodeIndex, rect.width, rect.height, rect.y);
			
			var newNode:SkylineNode = new SkylineNode();
			newNode.x = rect.x;
			newNode.y = rect.y + rect.height;
			newNode.width = rect.width;
			skyLine.insertAt(skylineNodeIndex, newNode);
			
			trace(newNode.x + newNode.width <= binWidth);
			trace(newNode.y <= binHeight);
			
			for(var i:int = skylineNodeIndex+1; i < skyLine.length; ++i)
			{
				trace(skyLine[i-1].x <= skyLine[i].x);
				
				if (skyLine[i].x < skyLine[i-1].x + skyLine[i-1].width)
				{
					var shrink:int = skyLine[i-1].x + skyLine[i-1].width - skyLine[i].x;
					
					skyLine[i].x += shrink;
					skyLine[i].width -= shrink;
					
					if (skyLine[i].width <= 0)
					{
						skyLine.splice(i,1);
						--i;
					}
					else
						break;
				}
				else
					break;
			}
			MergeSkylines();
		}
		
		private function MergeSkylines():void
		{
			for(var i:int = 0; i < skyLine.length-1; ++i)
				if (skyLine[i].y == skyLine[i+1].y)
				{
					skyLine[i].width += skyLine[i+1].width;
					skyLine.splice(i+1,1);
					--i;
				}
		}
		
		private function InsertBottomLeft(width:int, height:int):Rectangle
		{
			var bestHeight:int;
			var bestWidth:int;
			var bestIndex:int;
			var result:* = FindPositionForNewNodeBottomLeft(width, height, bestHeight, bestWidth, bestIndex);
			var newNode:Rectangle = result.node;
			bestHeight = result.bh;
			bestWidth = result.bw;
			bestIndex = result.bi;
			if (bestIndex != -1)
			{
				trace('InsertBottomLeft',disjointRects.Disjoint(newNode));
				
				// Perform the actual packing.
				AddSkylineLevel(bestIndex, newNode);
				
				usedSurfaceArea += width * height;
				if( Config.DEBUG){
					disjointRects.Add(newNode);
				}
				
			}
//			else
//				memset(&newNode, 0, sizeof(Rect));
			
			return newNode;
		}
		
		private function FindPositionForNewNodeBottomLeft( width:int, height:int, bestHeight:int, bestWidth:int, bestIndex:int):Object
		{
			bestHeight = int.MAX_VALUE;
			bestIndex = -1;
			// Used to break ties if there are nodes at the same level. Then pick the narrowest one.
			bestWidth = int.MAX_VALUE;
			var newNode:Rectangle = new Rectangle();
//			memset(&newNode, 0, sizeof(newNode));
			for(var i:int = 0; i < skyLine.length; ++i)
			{
				var y:int;
				if (RectangleFits(i, width, height, y))
				{
					if (y + height < bestHeight || (y + height == bestHeight && skyLine[i].width < bestWidth))
					{
						bestHeight = y + height;
						bestIndex = i;
						bestWidth = skyLine[i].width;
						newNode.x = skyLine[i].x;
						newNode.y = y;
						newNode.width = width;
						newNode.height = height;
						trace(disjointRects.Disjoint(newNode));
					}
				}
				if (RectangleFits(i, height, width, y))
				{
					if (y + width < bestHeight || (y + width == bestHeight && skyLine[i].width < bestWidth))
					{
						bestHeight = y + width;
						bestIndex = i;
						bestWidth = skyLine[i].width;
						newNode.x = skyLine[i].x;
						newNode.y = y;
						newNode.width = height;
						newNode.height = width;
						trace(disjointRects.Disjoint(newNode));
					}
				}
			}
			
			return {node:newNode,bh:bestHeight, bw:bestWidth,bi:bestIndex};
		}
		
		private function InsertMinWaste(width:int, height:int):Rectangle
		{
			var bestHeight:int;
			var bestWastedArea:int;
			var bestIndex:int;
			var newNode:Rectangle;
			var result:* = FindPositionForNewNodeMinWaste(width, height, bestHeight, bestWastedArea, bestIndex);
			newNode = result.node;
			bestHeight = result.r0;
			bestWastedArea = result.r1;
			bestIndex = result.r2;
			
			if (bestIndex != -1)
			{
				trace(disjointRects.Disjoint(newNode));
				
				// Perform the actual packing.
				AddSkylineLevel(bestIndex, newNode);
				
				usedSurfaceArea += width * height;
				if( Config.DEBUG)
					disjointRects.Add(newNode);
			}
//			else
//				memset(&newNode, 0, sizeof(newNode));
			
			return newNode;
		}
		
		private function FindPositionForNewNodeMinWaste(width:int, height:int, bestHeight:int, bestWastedArea:int, bestIndex:int):Object
		{
			bestHeight = int.MAX_VALUE;
			bestWastedArea = int.MAX_VALUE;
			bestIndex = -1;
			var newNode:Rectangle;
//			memset(&newNode, 0, sizeof(newNode));
			for(var i:int = 0; i < skyLine.length; ++i)
			{
				var y:int;
				var wastedArea:int;
				var result:* = RectangleFits1(i, width, height, y, wastedArea);
				y = result.y;
				wastedArea = result.w;
				if (result.f)
				{
					if (wastedArea < bestWastedArea || (wastedArea == bestWastedArea && y + height < bestHeight))
					{
						bestHeight = y + height;
						bestWastedArea = wastedArea;
						bestIndex = i;
						newNode.x = skyLine[i].x;
						newNode.y = y;
						newNode.width = width;
						newNode.height = height;
						trace(disjointRects.Disjoint(newNode));
					}
				}
				var result:* = RectangleFits1(i, height, width, y, wastedArea);
				y = result.y;
				wastedArea = result.w;
				if (result.f)
				{
					if (wastedArea < bestWastedArea || (wastedArea == bestWastedArea && y + width < bestHeight))
					{
						bestHeight = y + width;
						bestWastedArea = wastedArea;
						bestIndex = i;
						newNode.x = skyLine[i].x;
						newNode.y = y;
						newNode.width = height;
						newNode.height = width;
						trace(disjointRects.Disjoint(newNode));
					}
				}
			}
			
			return {node:newNode,r0:bestHeight , r1:bestWastedArea , r2:bestIndex};
		}
		
		/// Computes the ratio of used surface area.
		public function Occupancy():Number
		{
			return usedSurfaceArea / (binWidth * binHeight);
		}
	}
	
}